import java.util.ArrayList;
import java.util.List;

public class test03 {
    private static int count = 0;
//    private static List<List<Integer>> allWays = new ArrayList<>();

    public static void main(String[] args) {
        int steps = 6;
        backtrackSteps(steps, new ArrayList<>(), new ArrayList<>());
        System.out.println("总走法数：" + count);
        count = 0;
    }

    private static void backtrackSteps(int steps, List<Integer> cur,List<List<Integer>> path) {
        // 走完所有台阶
        if (steps == 0) {
            path.add(new ArrayList<>(cur));
            count++;
            return;
        }
        // 尝试走1级
        if (steps >= 1) {
            cur.add(1);
            backtrackSteps(steps - 1, cur, path);
            cur.remove(cur.size() - 1);
        }
        if (steps >= 2) {
            cur.add(2);
            backtrackSteps(steps - 2, cur,path);
            cur.remove(cur.size() - 1);
        }
    }
}